use std::rc::Rc;
use std::cell::RefCell;
use std::rc::Weak;

#[derive(Debug)]
struct TYPE
{
	v1 : i32,
	v2 : i32,
	v3 : i32
}

fn main()
{
	print!("{}[2J", 27 as char);	//clear
	bx();
	println!("=====================");
	rc();
	println!("=====================");
	refcell();
	println!("=====================");
	cyclic();
	println!("=====================");
	bt();
	println!("=====================");
	bt2();
}

fn bx()
{
	let t = TYPE {v1:1, v2:2, v3:3};
	let mut p = Box::new(t);		//执行完后，t不可访问
	println!("{},{}", p.v1, (*p).v1);	//两种表达一致，会自动解引用
	p.v1 = 123;
	println!("{}", p.v1);
}

fn rc()
{
	let t = TYPE {v1:1, v2:2, v3:3};
	let mut p = Rc::new(t);		//执行完后，t不可访问
//	p.v1 = 123;		不能修改Rc指针指向的内容，即使Rc指针是mut
	let c1 = Rc::clone(&p);
	let c2 = Rc::clone(&p);
	let cc = Rc::clone(&c1);
	println!("{}, {}, {}, {}", p.v1, c1.v1, c2.v1, cc.v1);
}

fn refcell()
{
	let t = TYPE {v1:1, v2:2, v3:3};	//指针所引用的变量无需mut(当然mut也无妨)，通过RefCell可以修改其内容
	let p = RefCell::new(t);			//执行完后，t不可访问
	/*
	同一个RefCell变量p，若生成了borrow或borrow_mut的实名变量，则在此变量消失前不能再调用p.borrow或borrow_mut
	所以下面代码如果“一”和“二”的位置调换，运行时则会panic
	*/
	{
		//一一一一一一
		p.borrow_mut().v1 = 123;			//p.borrow_mut结果存放在隐性变量，此句之后变量消失
		p.borrow_mut().v2 = 321;			//所以之后仍可以继续调用borrow或borrow_mut
		println!("{:?}", p.borrow());		//p.borrow结果存放在隐性变量，此句之后变量消失

		//二二二二二二
		let mut rf = p.borrow_mut();		//生成实名变量(borrow与borrow_mut均如此)，从此不能再调用p.borrow或p.borrow_mut。直至离开rf的作用域
		rf.v1 += rf.v2;
		println!("{:?}", rf);
		
//		p.borrow(); p.borrow_mut();				//这里会panic，因为有个rf
	}
	p.borrow(); p.borrow_mut();				//这里不会panic，因为rf已经消失了
}

#[macro_export]
macro_rules! DATA_POINTER
{
	($v : expr) =>		//数据结构里面的节点
	(
		Rc::new($v)
	);
}

#[macro_export]
macro_rules! POINTER_SINGLE
{
	($t : tt) =>	//类型
	(
		RefCell<Weak<$t>>
	);
	
	() =>			//None值
	(
		RefCell::new(Weak::new())
	);
}

#[macro_export]
macro_rules! POINTER_CONTAINER
{
	($container : tt, $t : tt) =>		//类型，其中container是容器类型，为vector或hashmap。t是容器元素的类型
	(
		RefCell<$container<Weak<$t>>>
	);
	
	($container : tt) =>				//None值
	(
		RefCell::new($container::new())
	);
}

#[macro_export]
macro_rules! POINTER_GET
{
	($me : tt) =>						//只读获取POINTER_SINGLE包裹的值
	(
		$me.borrow()	//RefCell
		   .upgrade()	//Weak
	)
}

#[macro_export]
macro_rules! POINTER_OP_LEFT
{
	($me : tt) =>
	(
		*$me.borrow_mut()
	)
}

#[macro_export]
macro_rules! POINTER_OP_RIGHT
{
	($v : tt) =>
	(
		Rc::downgrade(&$v);
	)
}

fn cyclic()
{
/*
1	节点定义中，凡是存在环回引用可能的指针用POINTER_SINGLE!(目标数据类型)或POINTER_CONTAINER!(Vec或Hashmap，目标数据类型)包裹
2	POINTER_SINGLE对应的节点以DATA_POINTER包裹实际数据来存放。取回包裹内的实际数据用POINTER_GET，类型为Option<_>
3	对引用赋值时，左值用POINTER_OP_LEFT，右值用POINTER_OP_RIGHT
4	POINTER_CONTAINER对应的节点以vec!或hashmap作为容器存放，容器内部元素的存放和取回与2和3所述一致
*/

	#[derive(Debug)]
	struct PERSON {name:&'static str, company:POINTER_SINGLE!(COMPANY)}
	#[derive(Debug)]
	struct COMPANY {name:&'static str, leader:POINTER_SINGLE!(PERSON), employees:POINTER_CONTAINER!(Vec, PERSON)}
	
	let person = DATA_POINTER!(PERSON {name:"游民", company: POINTER_SINGLE!()});
	let corp : Option<_> = POINTER_GET!((person.company));
	println!("{}的公司是{:?}", person.name, corp);

	let corp = DATA_POINTER!(COMPANY {name: "公司", leader: POINTER_SINGLE!(), employees: POINTER_CONTAINER!(Vec)});
	let leader = DATA_POINTER!(PERSON {name: "张三", company: POINTER_SINGLE!()});
	let employee = DATA_POINTER!(PERSON {name: "李四", company: POINTER_SINGLE!()});

	POINTER_OP_LEFT!((corp.leader)) = POINTER_OP_RIGHT!(leader);
	POINTER_OP_LEFT!((corp.employees)) = vec![POINTER_OP_RIGHT!(leader), POINTER_OP_RIGHT!(employee)];
	POINTER_OP_LEFT!((leader.company)) = POINTER_OP_RIGHT!(corp);
	POINTER_OP_LEFT!((employee.company)) = POINTER_OP_RIGHT!(corp);
	
	println!("----------------");
	
	println!("{:?}", POINTER_GET!((corp.leader)));
	println!("{:?}", POINTER_GET!((leader.company)));
	println!("{:?}", POINTER_GET!((employee.company)));

	if let Some(ldr) = POINTER_GET!((corp.leader))
	{
		println!("{}的领导是{}，总共有以下员工：", corp.name, ldr.name);
	}
	
	let company = POINTER_GET!((employee.company)).unwrap();
	let employees = company.employees.borrow();
	for weak in employees.iter() {println!("{:?}", weak.upgrade().unwrap());}
	
}

fn bt()
{
	#[derive(Debug)]
	struct NODE {id: u64, left: POINTER_SINGLE!(NODE), right: POINTER_SINGLE!(NODE)}
	
	impl NODE
	{
		pub fn walk_pre(&self)
		{
			print!("-{}-", self.id);
			if let Some(leaf) = POINTER_GET!((self.left)) {leaf.walk_pre();}
			if let Some(leaf) = POINTER_GET!((self.right)) {leaf.walk_pre();}
		}
		
		pub fn walk_mid(&self)
		{
			if let Some(leaf) = POINTER_GET!((self.left)) {leaf.walk_mid();}
			print!("-{}-", self.id);
			if let Some(leaf) = POINTER_GET!((self.right)) {leaf.walk_mid();}
		}
		
		pub fn walk_post(&self)
		{
			if let Some(leaf) = POINTER_GET!((self.left)) {leaf.walk_post();}
			if let Some(leaf) = POINTER_GET!((self.right)) {leaf.walk_post();}
			print!("-{}-", self.id);
		}
		
		pub fn point_node(&self, path : String, exists : &mut String) -> Option<Rc<NODE>>
		{
			let nil : Option<Rc<NODE>> = None;
			
			if path.len() == 0 {return nil;}
			
			let sub : String = path.chars().skip(1).collect();
			
			if path.starts_with("L")
			{
				match POINTER_GET!((self.left))
				{
					Some(leaf) =>
						{
							exists.push('L');
							if sub.len() == 0 {Some(leaf)} else {leaf.point_node(sub, exists)}
						},
					_ => nil
				}
			}
			else
			{
				match POINTER_GET!((self.right))
				{
					Some(leaf) =>
						{
							exists.push('R');
							if sub.len() == 0 {Some(leaf)} else {leaf.point_node(sub, exists)}
						},
					_ => nil
				}
			}
		}
	}

	let root = DATA_POINTER!(NODE {id: 5, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	
	let leaf = DATA_POINTER!(NODE {id: 50, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((root.left)) = POINTER_OP_RIGHT!(leaf);
	
	let leaf = DATA_POINTER!(NODE {id: 51, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((root.right)) = POINTER_OP_RIGHT!(leaf);
	
	let node = POINTER_GET!((root.left)).unwrap();
	let leaf = DATA_POINTER!(NODE {id: 500, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((node.left)) = POINTER_OP_RIGHT!(leaf);
	
	let leaf = DATA_POINTER!(NODE {id: 501, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((node.right)) = POINTER_OP_RIGHT!(leaf);
	
	let node = POINTER_GET!((node.left)).unwrap();
	let leaf = DATA_POINTER!(NODE {id: 5001, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((node.right)) = POINTER_OP_RIGHT!(leaf);
	
	let node = POINTER_GET!((node.right)).unwrap();
	let leaf = DATA_POINTER!(NODE {id: 50010, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((node.left)) = POINTER_OP_RIGHT!(leaf);
	
	let leaf = DATA_POINTER!(NODE {id: 50011, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((node.right)) = POINTER_OP_RIGHT!(leaf);
	
	let node = POINTER_GET!((root.right)).unwrap();
	let leaf = DATA_POINTER!(NODE {id: 510, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((node.left)) = POINTER_OP_RIGHT!(leaf);
	
	let node = POINTER_GET!((node.left)).unwrap();
	let leaf = DATA_POINTER!(NODE {id: 5101, left: POINTER_SINGLE!(), right: POINTER_SINGLE!()});
	POINTER_OP_LEFT!((node.right)) = POINTER_OP_RIGHT!(leaf);
	
	print!("前序遍历：");
	root.walk_pre();
	println!();
	
	print!("中序遍历：");
	root.walk_mid();
	println!();
	
	print!("后序遍历：");
	root.walk_post();
	println!();
	
	let mut longest : String = String::from("");
	let node = root.point_node("LLRRLR".to_string(), &mut longest);
	println!("{:?},  {}", node, longest);
}

fn bt2()
{
	#[derive(Debug, Clone)]
	struct NODE {id: u64, left: Option<Box<NODE>>, right: Option<Box<NODE>>}
	
	impl NODE
	{
		pub fn walk_pre(&self)
		{
			print!("-{}-", self.id);
			if let Some(ref leaf) = self.left {leaf.walk_pre();}
			if let Some(ref leaf) = self.right {leaf.walk_pre();}
		}
		
		pub fn walk_mid(&self)
		{
			if let Some(ref leaf) = self.left {leaf.walk_mid();}
			print!("-{}-", self.id);
			if let Some(ref leaf) = self.right {leaf.walk_mid();}
		}
		
		pub fn walk_post(&self)
		{
			if let Some(ref leaf) = self.left {leaf.walk_post();}
			if let Some(ref leaf) = self.right {leaf.walk_post();}
			print!("-{}-", self.id);
		}
	
		pub fn grow(&mut self, path : String) -> &mut Self
		{
			let sub : String = path.chars().skip(1).collect();
			
			if path.starts_with("L")
			{
				if let Some(ref mut leaf) = self.left
				{
					if path.len() == 1 {return self;}
					leaf.grow(sub);
				}	
				else
				{
					let leaf = NODE {id: self.id * 10, left: None, right: None};
					self.left = Some(Box::new(leaf));
					if let Some(ref mut leaf) = self.left
					{
						leaf.grow(sub);
					}
				}
			}
			else if path.starts_with("R")
			{
				if let Some(ref mut leaf) = self.right
				{
					if path.len() == 1 {return self;}
					leaf.grow(sub);
				}
				else
				{
					let leaf = NODE {id: self.id * 10 + 1, left: None, right: None};
					self.right = Some(Box::new(leaf));
					if let Some(ref mut leaf) = self.right
					{
						leaf.grow(sub);
					}
				}
			}
			
			self
		}
		
		pub fn path2node(self, path : String, exists : &mut String) -> Option<Box<NODE>>
		{
			let nil : Option<Box<NODE>> = None;
			let mut node : Box<NODE> = Box::new(self);
			
			if path.len() == 0
			{
				return Some(node);
			}
			
			for c in path.chars()
			{
				if c == 'L'
				{
					if let Some(ref leaf) = node.left
					{
						exists.push(c);
						node = node.left.unwrap();
					}
					else
					{
						return nil;
					}
				}
				else if c == 'R'
				{
					if let Some(ref leaf) = node.right
					{
						exists.push(c);
						node = node.right.unwrap();
					}
					else
					{
						return nil;
					}
				}
			}
			
			Some(node)
		}
		
		pub fn path2node_recursion(self, path : String, exists : &mut String) -> Option<Box<NODE>>
		{
			if path.len() == 0
			{
				return Some(Box::new(self));
			}
			
			let nil : Option<Box<NODE>> = None;
			let sub : String = path.chars().skip(1).collect();
			
			if path.starts_with("L")
			{
				if let Some(leaf) = self.left
				{
					exists.push('L');
					return leaf.path2node_recursion(sub, exists);
				}
				else
				{
					return nil;
				}
			}
			else if path.starts_with("R")
			{
				if let Some(leaf) = self.right
				{
					exists.push('R');
					return leaf.path2node_recursion(sub, exists);
				}
				else
				{
					return nil;
				}
			}
			
			nil
		}
	}
	
	let mut root = NODE {id: 6, left: None, right: None};
	root.grow("LLRL".to_string())
		.grow("LLRR".to_string())
		.grow("LR".to_string())
		.grow("RLR".to_string());
	
	print!("前序遍历：");
	root.walk_pre();
	println!();
	
	print!("中序遍历：");
	root.walk_mid();
	println!();
	
	print!("后序遍历：");
	root.walk_post();
	println!();

	//////下面调用path2node和path2node_recursion时要用root.clone()，否则只能调用其中一个，不能一次性调用多个或多次
	//////因为fn(self)拿了self(即root)的控制权不归还，所以只能传递副本来调用
	//////而之前的grow和walk_XXX是fn(&self)，是借用，借完后归还控制权，所以不用克隆也可以无限使用
	//////要struct支持clone()，则要在定义struct前加#[derive(Clone)]
	
	let mut longest = "".to_string();
	let node = root.clone().path2node("LLRRLR".to_string(), &mut longest);
	println!("{:?},  {}", node, longest);

	let mut longest = "".to_string();
	let node = root.clone().path2node_recursion("LLRRLR".to_string(), &mut longest);
	println!("{:?},  {}", node, longest);
	
}